#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    bool _isSymmetric(TreeNode* root1, TreeNode* root2){
        if (!root1 && !root2){
            return true;
        }else if (!root1 || !root2){
            return false;
        }else if (root1->val != root2->val){
            return false;
        }
        return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
    }

public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return _isSymmetric(root->left, root->right);
    }
};

TreeNode* createTree(int deepth, uint32_t max)
{
    if (deepth <= 0) return NULL;
    int value = rand()%max;
    TreeNode* root = new TreeNode(value);
    TreeNode* ref = root;
    ref->left = createTree(deepth-1, max);
    ref->right = createTree(deepth-1, max);
    return root;
}

void printTree(TreeNode* root)
{
    if (!root) return;
    printf("%d ", root->val);
    printTree(root->left);
    printTree(root->right);
}

int main()
{
    Solution su;
    TreeNode* tree;
    srand(clock());
    tree = createTree(5, 20);
    printTree(tree);
    printf("\r\n");
    bool result = su.isSymmetric(tree);
    printf("the result is %d\r\n", result);
    return 0;
}

